Програма вступного іспиту з дисципліни «МАТЕМАТИЧНІ МЕТОДИ ДОСЛІДЖЕННЯ ОПЕРАЦІЙ» Розділ 1. ВСТУП. ОСНОВНІ ПОНЯТТЯ ТА МЕТОДОЛОГІЯ ДО §1. Історія розвитку та використання методів дослідження операцій (ДО). Наукова суть ДО. Області практичних застосувань методів ДО та мета його вивчення. §2. Основні поняття ДО: операція, оперуюча сторона, стратегія, стан, діючі фактори операції, критерії ефективності. §3. Методологія проведення операційного дослідження: визначення мети; складання плану розробки; формулювання проблеми; побудова математичної моделі; синтез та (або) обгрунтування математичного методу; опрацювання інформації; перевірка адекватності моделі; реалізація результатів. §4. Пряма та обернена задачі ДО. Класифікація моделей ДО. Поняття про детерміновані та стохастичні моделі ДО і основні підходи до їх розв’язування. §5. Проблема багатокритеріальності та її розв’язування; згортка критеріїв, переведення критеріїв в обмеження, методи послідовних поступок, діалогові методи. Розділ 2. КЛАСИЧНІ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ (ЛП) §1. Поняття про задачу математичного програмування (МП). Загальна постановка та класифікація задач МП, поняття складності алгоритмів розв’язування задач МП. Побудова математичних моделей задач ДО. §2. Лінійні моделі та зв’язані з ними спрощення дійсності: пропорційність і адитивність. Загальна канонічна форма задачі ЛП. §3. Графічне розв’язування задач ЛП. Поняття про основні задачі аналізу лінійних моделей на чутливість: статус та допустимі межі зміни ресурсів, цінність ресурсів, чутливість функції мети. §4. Базисні розв’язки задачі ЛП. Основні теореми ЛП. Алгоритм симплекс-методу та його таблична форма. §5. Умови оптимальності та допустимості. Особливі випадки симплекс-методу. Методи знаходження початкового базису: двоетапний та метод великих штрафів. §6. Двоїстість у задачах ЛП. Поняття прямої та двоїстої задач ЛП. Основні теореми двоїстості. Економічна інтерпретація двоїстості. §7. Поняття про методи розв’язування задач ЛП великої розмірності та особливої структури. Методи декомпозиції, розріджені матриці, особливості реалізації алгоритмів. §8. Модель транспортної задачі ЛП. Приклади транспортних задач (ТЗ). Методи побудови опорного плану ТЗ: північно-західного кута, мінімального елементу, евристичний метод Фойгеля. §9. Методи знаходження оптимального плану ТЗ (метод потенціалів і розподільчий). Теореми про потенціали. §10. Транспортні задачі з особливостями в формулюванні, їх виродженість. Розділ 3. ЗАДАЧІ НА МЕРЕЖАХ §1. Загальні поняття мережі, потоку. Властивості потоку. Теорема Форда-Фалкерсона про максимальний потік і мінімальний розріз. §2. Постановка задачі про максимальний потік мінімальної вартості. Основні типи потокових задач як частинні випадки загальної. §3. Задача про найкоротший ланцюг. Алгоритм Дейкстри. §4. Задача про багатополюсний найкоротший ланцюг. Алгоритм Флойда. §5. Задача про знаходження максимального потоку та її застосування. Алгоритм розташування позначок. §6. Поняття про методи управління проектами. Послідовність розв’язування задач управління проектами. §7. Параметри мережі: ранні та пізні терміни здійснення подій і робіт, критичний шлях. Резерви часу подій і робіт. Метод критичного шляху (CRМ). §8. Схематичні моделі управління проектами. Метод PERT. Розділ 4. ЗАДАЧІ ШЛОЧИСЕЛЬНОГО ПРОГРАМУВАННЯ §1. Особливості цілочисельних задач. Цілочисельні моделі практичних задач. §2. Загальна характеристика основних груп методів розв’язування цілочисельних задач: відсічень, комбінаторних, евристичних. Принципи побудови евристичних алгоритмів. §3. Основні ідеї методів відсічень. Метод Гоморі, його недоліки. §4. Метод вектора спаду. Схема методу гілок і границь та її основні структурні елементи: стратегії розгалуження, границі та їх властивості, стратегія відтинання вузлів. §5. Проблеми представлення цілочисельних задач і процесу їх розв’язування в ЕОМ. Розділ 5. ТЕОРІЯ ІГОР §1. Основні поняття теорії ігор: учасники ...